package ventottoGiuDuemilaundici;

import positionList.BoundaryViolationException;
import positionList.InvalidPositionException;
import binaryTree.EmptyTreeException;
import binaryTree.NonEmptyTreeException;

public class HeapBinaryTree<E> {
	protected HNode<E> root; // reference to the root
	protected int size; // number of nodes

	/** Creates an empty binary tree. */
	public HeapBinaryTree() {
		root = null; // start with an empty tree
		size = 0;
	}

	/** Returns the number of nodes in the tree. */
	public int size() {
		return size;
	}

	/** Returns whether a node is internal. */
	public boolean isInternal(HNode<E> v) throws InvalidPositionException {
		return (hasLeft(v) || hasRight(v));
	}

	/** Returns whether a node is the root. */
	public boolean isRoot(HNode<E> v) throws InvalidPositionException {
		return (v == root());
	}

	/** Returns whether a node has a left child. */
	public boolean hasLeft(HNode<E> v) throws InvalidPositionException {
		return (v.getLeft() != null);
	}

	/** Returns the root of the tree. */
	public HNode<E> root() throws EmptyTreeException {
		if (root == null)
			throw new EmptyTreeException("The tree is empty");
		return root;
	}

	/** Returns the left child of a node. */
	public HNode<E> left(HNode<E> v) throws InvalidPositionException,
			BoundaryViolationException {
		HNode<E> leftPos = v.getLeft();
		if (leftPos == null)
			throw new BoundaryViolationException("No left child");
		return leftPos;
	}

	/** Returns the parent of a node. */
	public HNode<E> parent(HNode<E> v) throws InvalidPositionException,
			BoundaryViolationException {
		HNode<E> parentPos = v.getParent();
		if (parentPos == null)
			throw new BoundaryViolationException("No parent");
		return parentPos;
	}


	/** Replaces the element at a node. */
	public E replace(HNode<E> v, E o) throws InvalidPositionException {
		E temp = v.element();
		v.setElement(o);
		return temp;
	}


	// Additional update methods
	/** Adds a root node to an empty tree */
	public HNode<E> addRoot(int k, E e) throws NonEmptyTreeException {
		if (!isEmpty())
			throw new NonEmptyTreeException("Tree already has a root");
		size = 1;
		root = createNode(k, e, null, null, null);
		return root;
	}

	/** Inserts a left child at a given node. */
	public HNode<E> insertLeft(HNode<E> v, int k, E e) throws InvalidPositionException {
		HNode<E> leftPos = v.getLeft();
		if (leftPos != null)
			throw new InvalidPositionException("Node already has a left child");
		HNode<E> ww = createNode(k, e, v, null, null);
		v.setLeft(ww);
		size++;
		return ww;
	}
	
	/** Inserts a right child at a given node. */
	public HNode<E> insertRight(HNode<E> v, int k, E e) throws InvalidPositionException {
		HNode<E> rightPos = v.getRight();
		if (rightPos != null)
			throw new InvalidPositionException("Node already has a right child");
		HNode<E> ww = createNode(k, e, v, null, null);
		v.setRight(ww);
		size++;
		return ww;
	}

	/** Removes a node with zero or one child. */
	public E remove(HNode<E> v) throws InvalidPositionException {
		HNode<E> leftPos = v.getLeft();
		HNode<E> rightPos = v.getRight();
		if (leftPos != null && rightPos != null)
			throw new InvalidPositionException(
					"Cannot remove node with two children");
		HNode<E> ww; // the only child of v, if any
		if (leftPos != null)
			ww = leftPos;
		else if (rightPos != null)
			ww = rightPos;
		else
			// v is a leaf
			ww = null;
		if (v == root) { // v is the root
			if (ww != null)
				ww.setParent(null);
			root = ww;
		} else { // v is not the root
			HNode<E> uu = v.getParent();
			if (v == uu.getLeft())
				uu.setLeft(ww);
			else
				uu.setRight(ww);
			if (ww != null)
				ww.setParent(uu);
		}
		size--;
		return v.element();
	}


	/** Creates a new binary tree node */
	protected HNode<E> createNode(int key, E element, HNode<E> parent, HNode<E> left,
			HNode<E> right) {
		return new HNode<E>(key, element, parent, left, right);
	}


	/** Returns whether the tree is empty. */
	public boolean isEmpty() {
		return size == 0;
	}

	/** Returns the right child of a node. */
	public HNode<E> right(HNode<E> v) throws InvalidPositionException,
			BoundaryViolationException { // metodo non implementato
		return null;
	}

	/** Returns whether a node has a right child. */
	public boolean hasRight(HNode<E> v) throws InvalidPositionException { // metodo
																		// non
																		// implementato
		return false;
	}

	/** Returns whether a given node is external. */
	public boolean isExternal(HNode<E> v) throws InvalidPositionException { // metodo
																			// non
																			// implementato
		return false;
	}

}
